P4462「[CQOI2018]异或序列」

1. 题目

题目链接：P4462「[CQOI2018]异或序列」 。

题目描述

已知一个长度为n的整数数列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，给定查询参数 l,rl,r，问在 al,al+1,⋯ ,ara_l,a_{l+1},\cdots,a_r 区间内，有多少子序列满足异或和等于 kk。也就是说，对于所有的 x,yx,y（l≤x≤y≤rl \leq x \leq y \leq r），能够满足 ax⨁ax+1⨁⋯⨁ay=ka_x \bigoplus a_{x+1} \bigoplus \cdots \bigoplus a_y = k 的 x,yx,y 有多少组。

输入格式

输入文件第一行，为 33 个整数 n,m,kn,m,k。

第二行为空格分开的 nn 个整数，即 a1,a2,..ana_1,a_2,..a_n。

接下来 mm 行，每行两个整数 lj,rjl_j,r_j，表示一次查询。

输出格式

输出文件共 mm 行，对应每个查询的计算结果。

输入输出样例

输入 #1

1
2
3
4
5
6
7
4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

输出 #1

1
2
3
4
5
4
2
1
2
1

说明/提示

对于 30%30\% 的数据，1≤n,m≤10001 \leq n, m \leq 1000。

对于 100%100\% 的数据，1≤n,m≤105,0≤k,ai≤105,1≤lj≤rj≤n1 \leq n, m \leq 10^5, 0 \leq k, a_i \leq 10^5,1 \leq l_j \leq r_j \leq n。

2. 题解

分析

  • 首先需要了解异或运算的优美性质。
  1. 设 si=a1⨁a2⨁⋯⨁ais_i = a_1 \bigoplus a_2 \bigoplus \cdots \bigoplus a_i，则有

al⨁al+1⨁⋯⨁ar=sl−1⨁sr\begin{array}{c} a_l \bigoplus a_{l+1} \bigoplus \cdots \bigoplus a_r = s_{l-1} \bigoplus s_r \end{array}

  1. 假设 a⨁b=ca \bigoplus b = c，则有

a=b⨁cb=a⨁c\begin{array}{c} a = b \bigoplus c \\ b = a \bigoplus c \\ \end{array}

因此，对于原题，我们可以将其转换为：在区间 [l,r][l,r] 内，有多少对 sx−1,sys_{x-1},s_y（l≤x≤y≤rl \leq x \leq y \leq r）满足 sx−1⨁sy=ks_{x-1} \bigoplus s_y = k，其中，si=a1⨁⋯⨁ai−1s_i = a_1 \bigoplus \cdots \bigoplus a_{i-1}，即 ss 数组为 aa 数组的异或前缀和。

  • 然后计算一下时间复杂度，O(mn)O(m\sqrt{n}) 可以过，而且可以离线查询，因此可以考虑用莫队算法。接下的问题就是如何实现相邻查询区间的 O(1)O(1) 转移。

假设序列 ss 的长度为 nn，若已知 [l,r][l,r] 区间的答案为 ansl,rans_{l,r}，且 countcount 数组记录了数组 ss 在 [l,r][l,r] 区间中各个数的出现次数，则区间 [l,r+1][l,r+1]（其它三个相邻区间的分析类似）的答案为

ansl,r+1=ansl,r+count[s[r+1]k]\begin{array}{c} ans_{l,r+1} = ans_{l,r} + count[s[r+1]^k] \end{array}

因此，只要在区间改变时维护好 countcount 数组，就可实现相邻查询区间 O(1)O(1) 复杂度的转移。

注意

需要判断一下应该开的数组大小以及数据类型是否会溢出：

  • 数组大小：由于 0≤k,ai≤1050 \leq k, a_i \leq 10^5，因此它们之间的异或结果最大为 2⌊log⁡2105⌋+1−12^{\lfloor\log_2{10^5}\rfloor + 1} - 1，即异或的结果会超出 10510^5，但始终能用 ⌊log⁡2105⌋\lfloor\log_2{10^5}\rfloor 位二进制表示。而 ⌊log⁡2105⌋\lfloor\log_2{10^5}\rfloor 位二进制所能表示的最大数为 2⌊log⁡2105⌋+1−12^{\lfloor\log_2{10^5}\rfloor + 1} - 1，又 2⌊log⁡2105⌋+1−1≤2×105−12^{\lfloor\log_2{10^5}\rfloor + 1} - 1 \leq 2 \times 10^5 - 1，因此数组长度需要开到 2×1052 \times 10^5 才合适。
  • 数据类型：由于区间 [l,r][l,r] 中最多有 Cr−l+12C_{r-l+1}^2 种两两配对，且 r−l+1≤105r-l+1 \leq 10^5，因此 Cr−l+12<=5×104×(105−1)≈5×109C_{r-l+1}^2 <= 5 \times 10^4 \times (10^5 - 1) \approx 5 \times 10^9，所以 int 数据类型其实是不够用的，要用 long long。

虽然这道没有卡这两点，但不可忽略它们。另一道基本相同的题 CF617E XOR and Favorite Number 就考虑了这两点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
using namespace std;

#ifndef _MOBK_
#define _MOBK_
#define ll long long
#define il inline
#define re register
#define MAXN 200100

char buf[200];

il ll read() {
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

il void write(ll x) {
    ll cnt = 0;
    while(x || !cnt) {
        buf[cnt++] = (x%10) + 48;
        x /= 10;
    }
    while(cnt) {
        putchar(buf[--cnt]);
    }
    putchar('\n');
}

// 分块大小
ll bz;
// 莫队
struct MOBK {
    // 查询区间
    struct Query {
        ll l, r, idx;
        bool operator < (const Query q) const {
            return l/bz != q.l/bz ? l < q.l : 
                (l/bz) & 1 ? r < q.r : r > q.r;
        }
    };
    ll n, m;            // 数列长度，查询次数
    ll curans;          // 当前查询答案
    ll count[MAXN];     // 计数数组
    ll result[MAXN];    // 答案数组（具体问题具体分析）
    Query query[MAXN];  // 查询区间数组
    // 初始化
    MOBK() {
        curans = 0;
        memset(count, 0, sizeof(count));
        memset(query, 0, sizeof(query));
    }
    MOBK(int _n, int _m): n(_n), m(_m) {
        bz = (ll)sqrt(n);
        curans = 0;
        memset(count, 0, sizeof(count));
        memset(query, 0, sizeof(query));
    }
    // 区间长度增一
    il void add(ll x, ll k) {
        curans += count[x^k];
        ++count[x];
    }
    // 区间长度减一
    il void del(ll x, ll k) {
        --count[x];
        curans -= count[x^k];
        
    }
    // 求解答案
    void solver(ll *a, ll k) {
        sort(query, query+m);
        re ll l = query[0].l;
        re ll r = query[0].l-1;
        for(re ll i = 0; i < m; ++i) {
            while(r < query[i].r) {
                add(a[++r], k);
            }
            while(r > query[i].r) {
                del(a[r--], k);
            }
            while(l < query[i].l) {
                del(a[l++], k);
            }
            while(l > query[i].l) {
                add(a[--l], k);
            }
            result[query[i].idx] = curans;
        }
        for(ll i = 0; i < m; ++i) {
            write(result[i]);
        }
    }
};
#endif

int main()
{
    ll n = read();
    ll m = read();
    ll k = read();
    static ll a[MAXN] = {0};
    static MOBK mobk = MOBK(n, m);
    for(re ll i = 1; i <= n; ++i) {
        a[i] = read();
    }
    for(re ll i = 2; i <= n; ++i) {
        a[i] ^= a[i-1];
    }
    for(re ll i = 0; i < m; ++i) {
        mobk.query[i].l = read() - 1;
        mobk.query[i].r = read();
        mobk.query[i].idx = i;
    }
    mobk.solver(a, k);
    return 0;
}